package ahaArithmetic;

//Dijkstar 单源最短路径
public class DijkStar {

    static int n = 6;  //表示有6个节点
    static int map[][] = new int[][]{
            {1,2,1},
            {1,3,12},
            {2,3,9},
            {2,4,3},
            {3,5,5},
            {4,3,4},
            {4,5,13},
            {4,6,15},
            {5,6,4}
    };
    static int[][] map2 = new int[n][n];
    //单源最短路径 数组
    static int dis[] = new int[n];
    static int book[] = new int[n];
    //0,1 分别代表 节点和路径
    static int min[] = new int[]{0,9999};
    static int count = 0;

    public static void main(String[] args) {
        //初始化map2
        for(int j=0;j<n;j++){
            for(int k=0;k<n;k++){
                if(j!=k){
                    map2[j][k] = 9999;
                }
            }
        }
        //mp2赋值
        for (int x[]:map){
            map2[x[0]-1][x[1]-1] = x[2];
        }
        //初始化dis数组
        for(int i=0;i<n;i++){
            dis[i] = map2[0][i];
        }
        dijkStar();
    }

    public static void dijkStar(){

        while (count<n) {
            //搜寻本轮最小的
            for (int i = 1; i < n; i++) {
                if (dis[i] < min[1] && book[i] == 0) {
                    min[0] = i;
                    min[1] = dis[i];
                }
            }
            book[min[0]] = 1;
            count++;
            for (int i = 1; i < n; i++) {
                if (map2[0][i] > map2[0][min[0]] + map2[min[0]][i]) {
                    map2[0][i] = map2[0][min[0]] + map2[min[0]][i];
                    dis[i] = map2[0][i];
                }
            }
            min[1] = 9999;
        }
        print();
    }

    public static void print(){
        for(int x:dis){
            System.out.println(x);
        }
    }
}
